package algorithm.graph.adjacencymatrix;

import java.util.*;
import java.util.function.Consumer;

public class SPFA {
    AdjacencyMatrixGraph graph;

    public SPFA(AdjacencyMatrixGraph graph) {
        this.graph = graph;
    }

    public void findPath(int from, int to, Consumer<int[]> onFind) {
        int[][] graphData = graph.getGraphData();
        int[] dist = new int[graph.getNodeCount()];
        int[] pre = new int[graph.getNodeCount()];
        Arrays.fill(dist, -1);
        Arrays.fill(pre, -1);
        dist[to] = 0;
        Queue<Integer> toVisit = new ArrayDeque<>();
        toVisit.add(to);
        for (int i = 0; i < graph.getNodeCount(); i++) {
            while (!toVisit.isEmpty()) {
                int sourceId = toVisit.poll();
                for (int toUpdateNodeId = 0; toUpdateNodeId < graph.getNodeCount(); toUpdateNodeId++) {
                    if (graphData[toUpdateNodeId][sourceId] > 0) {
                        if (dist[sourceId] != -1) {
                            if (dist[toUpdateNodeId] == -1 || dist[sourceId] + graphData[sourceId][toUpdateNodeId] < dist[toUpdateNodeId]) {
                                dist[toUpdateNodeId] = dist[sourceId] + 1;
                                pre[toUpdateNodeId] = sourceId;
                                if (!toVisit.contains(toUpdateNodeId)) {
                                    toVisit.add(toUpdateNodeId);
                                }
                            }
                        }
                    }
                }
            }
        }
        List<Integer> path = new ArrayList<>();
        if (dist[from] != -1) {
            int temp = from;
            while (pre[temp] != -1) {
                path.add(temp);
                temp = pre[temp];
            }
            path.add(to);
        }
        onFind.accept(path.stream().mapToInt(it -> it).toArray());
    }
}
